Various data compression encoding techniques are used for efficiently storing and transferring data. Currently available data compression encoding techniques may be generally classified as variable length coding (VLC) or fixed length coding (FLC).
VLC performs a data encoding process such that a length of codeword used for coding data may vary in length. That is, in VLC, data is encoded by using codewords having different lengths based on occurrence probabilities of data. Hereinafter, a VLC compression encoding technique is explained in more detail.
Generally, compression of video and audio data includes a process of transforming time-domain data into frequency-domain data. In the transforming process, a Fourier transform may be used such that “n” values in the time domain are represented by “n” values in the frequency domain. The transform coding method can convert video or audio signals into transform coefficients, which are further classified into a DC coefficient and an AC coefficient. The DC coefficient represents an average value of a predetermined block of input signals and the AC coefficient represents a value corresponding to components of the predetermined block of input signals. The AC coefficient is configured such that the AC coefficient value converges to a constant value as the calculation number is increased. Therefore, data having high occurrence probability may be encoded as codewords having a length of one bit or two bits when VLC is applied. In this manner VLC encoding can decrease a length of codeword to economize the size of memory required to store encoded data.
In some cases, however, information loss may occur due to quantization. A bit-by-bit analysis from a first bit of encoded data can be used for VLC because lengths of codeword vary during a decoding process. In addition, headers can be used to indicate a start point and an end point of encoded data. A decoder can be used to analyze encoded data bit by bit in order to detect the start point and the end point of encoded data. Therefore, VLC decoding can utilize a large decoding circuit and/or more processing time to decode VLC data.
Alternatively, FLC can use codewords having a fixed length. An FLC decoder may analyze encoded data by a fixed number of bits because FLC uses fixed length codewords. Since headers indicating the start point and the end point of encoded data are not required, FLC decoding circuits are generally smaller than those used in decoding using VLC. Similarly, the processing time for decoding data encoded by FLC is generally less than that of data encoded by VLC.
FLC, however, assigns a fixed length codeword to data having a high occurrence probability, which results in relatively large blocks of encoded data. The large blocks may not be suitable for compressing data that contains significant data content such as video and audio signals.
Hereinafter, the effect of data compression that uses a disproportion in occurrence probabilities of data is explained. Consider the example where four kinds of data—“0” “1,” “2” and “3” are encoded using a two-bit fixed length binary codeword such as binary values “00,” “01,” “10” and “11.” A disproportion in occurrence probabilities of data may be considered so that codewords having different lengths are respectively assigned to each of the four kinds of data as shown in the following Table 1.
TABLE 1OccurrenceLength ofDataprobabilityCodewordcodeword00.60110.210220.1110330.11113
In this example, when a codeword having the fixed length is assigned to each kind of data, an average length of the codeword is 2.0 bits, as determined by the following equation:Average length of FLC codeword=2×0.6+2×0.2+2×0.1+2×0.1=2.0 (bits)
Applying VLC principles to the example above, when codewords having different length are assigned to each of the four kinds of data as shown in Table 1, an average length of codewords may be smaller than 2 bits as represented in the following equation:Average length of VLC codeword=1×0.6+2×0.2+3×0.1+3×0.1=1.6 (bits)Thus, although VLC can be advantageous for compressing data having a disproportion in occurrence probabilities, such as is often present in video or audio signals, the VLC may utilize more processing time in decoding encoded data compared with FLC. The additional processing time can be realized because bit-by-bit analysis from a first bit of encoded data may be performed due to the variable lengths of the codewords, such that detection of header indicating the start point and the end point of encoded data may be necessary.